/**
 * @param {number[]} nums
 * @return {boolean}
 */
// 基本动态规划
var canPartition = function(nums) {
    const sum = nums.reduce((pre, cur) => pre + cur)
    // 奇数直接返回false
    if(sum % 2 !== 0) return false
    let target = sum / 2
    const dp = new Array(len).fill().map(() => {
        return new Array(target + 1).fill(false)
    })
    if(nums[0] <= target) dp[0][nums[0]] = true
    let len = nums.length
    for(let i = 1; i < len; i++) {
        for(let j = 0; j <= target; j++) {
            dp[i][j] = dp[i - 1][j] // 先不看其他的，最少i - 1能做到的，i一定能做到
            if(nums[i] === j) {
                dp[i][j] = true
                continue
            }
            if(nums[i] < j) {
                dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i]]
            }
        }
    }
    return dp[len - 1][target]
};
// 通过滚动数组优化空间，思路类似于对于一维状态dp[i] = dp[i - 1] + dp[i -2]
// 这里当前状态只与前两个状态有关，那没必要初始化len的数组
// 对于二维也以这样的思路思考，当前行只与上一行有关系，那么只用初始化一行滚动即可
// 只有一行如果从前往后修改状态，由于后面的状态会用到前面的，所以第n轮计算时，会用到错误的状态
// 因此从后往前算状态
var canPartition = function(nums) {
    const sum = nums.reduce((pre, cur) => pre + cur)
    // 奇数直接返回false
    if(sum % 2 !== 0) return false
    let target = sum / 2
    const dp = new Array(target + 1).fill(false)
    if(nums[0] <= target) dp[nums[0]] = true
    let len = nums.length
    for(let i = 1; i < len; i++) {
        for(let j = target; j >= nums[i]; j--) {
            if(dp[target]) return true
            // if(j >= nums[i]) { // 把这个if放进for循环里面
            // 当j < nums[i]时，j只与上一轮j有关即dp[j] = dp[j]，所以不用考虑
                dp[j] = dp[j] || dp[j - nums[i]]
            // }
        }
    }
    return dp[target]
};